{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Split of Positive Even Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumEvenSplit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拆分成最多数目的正偶数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>finalSum</code>&nbsp;。请你将它拆分成若干个&nbsp;<strong>互不相同</strong> 的正偶数之和，且拆分出来的正偶数数目&nbsp;<strong>最多</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，给你&nbsp;<code>finalSum = 12</code>&nbsp;，那么这些拆分是&nbsp;<strong>符合要求</strong> 的（互不相同的正偶数且和为&nbsp;<code>finalSum</code>）：<code>(2 + 10)</code>&nbsp;，<code>(2 + 4 + 6)</code>&nbsp;和&nbsp;<code>(4 + 8)</code>&nbsp;。它们中，<code>(2 + 4 + 6)</code>&nbsp;包含最多数目的整数。注意&nbsp;<code>finalSum</code>&nbsp;不能拆分成&nbsp;<code>(2 + 2 + 4 + 4)</code>&nbsp;，因为拆分出来的整数必须互不相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个整数数组，表示将整数拆分成 <strong>最多</strong> 数目的正偶数数组。如果没有办法将&nbsp;<code>finalSum</code>&nbsp;进行拆分，请你返回一个&nbsp;<strong>空</strong>&nbsp;数组。你可以按 <b>任意</b>&nbsp;顺序返回这些整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>finalSum = 12\n",
    "<b>输出：</b>[2,4,6]\n",
    "<b>解释：</b>以下是一些符合要求的拆分：<code>(2 + 10)<span style=\"\">，</span></code><code>(2 + 4 + 6) </code>和 <code>(4 + 8) 。</code>\n",
    "(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。\n",
    "[2,6,4] ，[6,2,4] 等等也都是可行的解。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>finalSum = 7\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>没有办法将 finalSum 进行拆分。\n",
    "所以返回空数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>finalSum = 28\n",
    "<b>输出：</b>[6,8,2,12]\n",
    "<b>解释：</b>以下是一些符合要求的拆分：<code>(2 + 26)<span style=\"\">，</span></code><code>(6 + 8 + 2 + 12)</code> 和 <code>(4 + 24) 。</code>\n",
    "<code>(6 + 8 + 2 + 12)</code> 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。\n",
    "[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= finalSum &lt;= 10<sup>10</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-split-of-positive-even-integers](https://leetcode.cn/problems/maximum-split-of-positive-even-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-split-of-positive-even-integers](https://leetcode.cn/problems/maximum-split-of-positive-even-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12', '7', '28']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        tmp = 0\n",
    "        res = []\n",
    "        for i in range(1,finalSum // 2 + 1):\n",
    "            res.append(i * 2)\n",
    "            tmp += i * 2\n",
    "            if tmp > finalSum:\n",
    "                break\n",
    "            elif tmp == finalSum:\n",
    "                return res\n",
    "        remove = tmp - finalSum\n",
    "        if remove in res:\n",
    "            res.remove(remove)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2: return []\n",
    "        ans = []\n",
    "        i = 2\n",
    "        while i <= finalSum:\n",
    "            ans.append(i)\n",
    "            finalSum -= i\n",
    "            i += 2\n",
    "        ans[-1] += finalSum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2:\n",
    "            return []\n",
    "        i = 2\n",
    "        ans = []\n",
    "        while i <= finalSum:\n",
    "            ans.append(i)\n",
    "            finalSum -= i\n",
    "            i += 2\n",
    "        ans[-1] += finalSum\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        res = []\n",
    "        if finalSum % 2 > 0:\n",
    "            return res\n",
    "        i = 2\n",
    "        while i <= finalSum:\n",
    "            res.append(i)\n",
    "            finalSum -= i\n",
    "            i += 2\n",
    "        res[-1] += finalSum\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if finalSum % 2 != 0: return []\n",
    "\n",
    "\n",
    "        start = 2\n",
    "        res = []\n",
    "        while start <= finalSum:\n",
    "\n",
    "            res.append(start)\n",
    "            finalSum -= start\n",
    "            start += 2\n",
    "        res[-1] += finalSum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        ans=[]\n",
    "        if finalSum%2:return ans\n",
    "        i=2\n",
    "        while i<=finalSum:\n",
    "            ans.append(i)\n",
    "            finalSum-=i \n",
    "            i+=2\n",
    "        ans[-1]+=finalSum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        res = []\n",
    "        if finalSum % 2 == 1:\n",
    "            return res\n",
    "        i = 2\n",
    "        while i <= finalSum:\n",
    "            res.append(i)\n",
    "            finalSum -= i\n",
    "            i += 2\n",
    "        if finalSum > 0:\n",
    "            res[-1] += finalSum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        \"\"\"\n",
    "        栈\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        i = 2\n",
    "\n",
    "        # 每一次迭代都保证i和前面不同\n",
    "        while i <= finalSum:\n",
    "            ans.append(i)\n",
    "            finalSum -= i\n",
    "            i += 2\n",
    "\n",
    "        ans[-1] += finalSum\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum & 1:\n",
    "            return []\n",
    "        cur = 2\n",
    "        ans = []\n",
    "        while finalSum > cur << 1:\n",
    "            finalSum -= cur\n",
    "            ans.append(cur)\n",
    "            cur += 2\n",
    "        ans.append(finalSum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        ans = []\n",
    "        if finalSum & 1:\n",
    "            return ans\n",
    "        cur = 2\n",
    "        while cur <= finalSum:\n",
    "            ans.append(cur)\n",
    "            finalSum -= cur\n",
    "            cur += 2\n",
    "        ans[-1] += finalSum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        # if finalSum % 2 :\n",
    "        #     return []\n",
    "        # res = []\n",
    "        # i = 2\n",
    "        # while finalSum >= i :\n",
    "        #     finalSum -= i\n",
    "        #     res.append(i)\n",
    "        #     i += 2\n",
    "        # res[-1] += finalSum\n",
    "        # return res            \n",
    "\n",
    "        if finalSum % 2 :\n",
    "            return []\n",
    "        n = (isqrt(finalSum * 4 + 1) - 1) // 2\n",
    "        res = list(range(2, 2 * n + 2, 2))\n",
    "        res[-1] = finalSum - n * (n - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        # 2 + 4 + ... + n < finalSum，求根公式\n",
    "        n = isqrt(4 * finalSum + 1) - 1\n",
    "        n -= n % 2\n",
    "        n_sum = (2 + n) * n >> 2\n",
    "        res = [*range(2, n + 1 , 2)]\n",
    "        res[-1] += finalSum - n_sum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        # if finalSum % 2 :\n",
    "        #     return []\n",
    "        # res = []\n",
    "        # i = 2\n",
    "        # while finalSum >= i :\n",
    "        #     finalSum -= i\n",
    "        #     res.append(i)\n",
    "        #     i += 2\n",
    "        # res[-1] += finalSum\n",
    "        # return res            \n",
    "\n",
    "        # if finalSum % 2 :\n",
    "        #     return []\n",
    "        # n = (isqrt(finalSum * 4 + 1) - 1) // 2\n",
    "        # res = list(range(2, 2 * n + 2, 2))\n",
    "        # res[-1] = finalSum - n * (n - 1)\n",
    "        # return res\n",
    "\n",
    "        if finalSum % 2:\n",
    "            return []\n",
    "        n0 = finalSum\n",
    "        while True:\n",
    "            n1 = (n0 ** 2 + finalSum) / (2 * n0+1)\n",
    "            if n0 - n1 < 1e-8:\n",
    "                break\n",
    "            n0 = n1\n",
    "        n = int(n0)\n",
    "        # return [n]\n",
    "        ans = list(range(2, 2*(n+1), 2))\n",
    "        ans[-1] = finalSum - n * (n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2==1:\n",
    "            return []\n",
    "        # print(finalSum//2)\n",
    "        sum_ = 0\n",
    "        for i in range(finalSum//2+1):\n",
    "\n",
    "            sum_ = sum_+i*2 \n",
    "            if sum_>finalSum:\n",
    "                \n",
    "                return [j*2 for j in range(1,i-1)]+[i*2-(sum_-finalSum)+(i-1)*2]\n",
    "            elif sum_==finalSum:\n",
    "                return [j*2 for j in range(1,i+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2:return []\n",
    "        Res = [0]\n",
    "        v = 2\n",
    "        while finalSum >= v:\n",
    "            finalSum -= v\n",
    "            Res.append(v)\n",
    "            v += 2\n",
    "        Res[-1] += finalSum\n",
    "        return Res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum & 1:\n",
    "            return []\n",
    "        \n",
    "        res = [ 0 ]\n",
    "        while finalSum / 2 > res[-1] + 2:\n",
    "            res.append(res[-1] + 2)\n",
    "            finalSum -= res[-1]\n",
    "        if finalSum:\n",
    "            res.append(finalSum)\n",
    "\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2:return []\n",
    "        i = 2\n",
    "        cur_sum = 0\n",
    "        res = []\n",
    "        while cur_sum<=finalSum:\n",
    "            res.append(i)\n",
    "            cur_sum+=i\n",
    "            i+=2\n",
    "        cur_sum-=res[-1]\n",
    "        res[-2]+=(finalSum-cur_sum)\n",
    "        return res[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, final_sum: int) -> List[int]:\n",
    "        # n * (n + 1) <= S => n^2 + n - S <= 0 sqrt(1 + 4*S) / 2\n",
    "        if final_sum & 1 == 1:\n",
    "            return []\n",
    "        n = int((math.sqrt(1 + 4 * final_sum) - 1) / 2)\n",
    "        return [i * 2 for i in range(1, n)] + [final_sum - n * (n - 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if( finalSum % 2 > 0):\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        i = 2\n",
    "        while( i <= finalSum):\n",
    "            if( finalSum >= i):\n",
    "                res.append(i)\n",
    "                finalSum = finalSum - i\n",
    "            i = i + 2\n",
    "        \n",
    "        res[-1] = res[-1] + finalSum\n",
    "        print(res)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2: return []\n",
    "        l, r = 1, finalSum\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if m * (m + 1) <= finalSum:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        if 2 * (m - 1) >= finalSum - (m - 1) * m:\n",
    "            m -= 1\n",
    "        return [2 * i for i in range(1, m)] + [finalSum - (m - 1) * m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2==1:\n",
    "            return []\n",
    "        rlt=0\n",
    "        i=0\n",
    "        while rlt<=finalSum:\n",
    "            rlt+=i*2\n",
    "            #print(rlt,i)\n",
    "            i+=1\n",
    "        rlt_num=i-2\n",
    "        i=1\n",
    "        rlt_list=[]\n",
    "        while rlt_num-i>0:\n",
    "            finalSum-=i*2\n",
    "            rlt_list.append(i*2)\n",
    "            i+=1\n",
    "        rlt_list.append(finalSum)\n",
    "        print(rlt_list)\n",
    "        return rlt_list\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        \n",
    "        if finalSum & 1:return []\n",
    "\n",
    "        i = 2\n",
    "        res = []\n",
    "        while i<=finalSum:\n",
    "            res.append(i)\n",
    "            finalSum-=i\n",
    "            i+=2\n",
    "        print(res)\n",
    "        res[-1]+=finalSum\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0: return []\n",
    "        odd = 2\n",
    "        arr = []\n",
    "        now = 0\n",
    "        while True:\n",
    "            now += odd\n",
    "            arr.append(odd)\n",
    "            if now == finalSum: return arr\n",
    "            if now > finalSum:\n",
    "                arr.remove(now - finalSum)\n",
    "                return arr\n",
    "            odd += 2\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        tmp = 0\n",
    "        res = []\n",
    "        for i in range(1,finalSum // 2 + 1):\n",
    "            tmp_num = i * 2\n",
    "            res.append(tmp_num)\n",
    "            tmp += tmp_num\n",
    "            if tmp > finalSum:\n",
    "                break\n",
    "            elif tmp == finalSum:\n",
    "                return res\n",
    "        remove = tmp - finalSum\n",
    "        if remove in res:\n",
    "            res.remove(remove)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2!=0:\n",
    "            return []\n",
    "        total=0\n",
    "        count=0\n",
    "        re=[]\n",
    "        while total<=finalSum:\n",
    "            count+=1\n",
    "            total+=2*count\n",
    "            re.append(2*count)\n",
    "        re=re[:-2]\n",
    "        re.append(finalSum-sum(re))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2!=0:\n",
    "            return []\n",
    "        total=0\n",
    "\n",
    "\n",
    "        count=0\n",
    "        re=[]\n",
    "        while total<=finalSum:\n",
    "            count+=1\n",
    "            total+=2*count\n",
    "            re.append(2*count)\n",
    "        re=re[:-2]\n",
    "        re.append(finalSum-sum(re))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2!=0:\n",
    "            return []\n",
    "        total=0\n",
    "\n",
    "\n",
    "        count=0\n",
    "        re=[]\n",
    "        while total<=finalSum:\n",
    "            count+=1\n",
    "            total+=2*count\n",
    "            re.append(2*count)\n",
    "        re=re[:-2]\n",
    "        re.append(finalSum-sum(re))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2!=0:\n",
    "            return []\n",
    "        total=0\n",
    "\n",
    "\n",
    "        count=0\n",
    "        re=[]\n",
    "        while total<=finalSum:\n",
    "            count+=1\n",
    "            total+=2*count\n",
    "            re.append(2*count)\n",
    "        re=re[:-2]\n",
    "        re.append(finalSum-sum(re))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        # 28 -> [2,26],[4,24],[6,22],[8,20],[10,18],[12,16],[14,14]\n",
    "        # 贪心-优先分出来更小的偶数\n",
    "        # 这样也就是2+4+6...+t等差数列\n",
    "        if finalSum % 2:\n",
    "            return []\n",
    "        n = int(pow(finalSum, 0.5))\n",
    "        \n",
    "        if n * (n + 1) == finalSum:\n",
    "            return list(range(2, 2 * n + 1, 2))\n",
    "        elif n * (n + 1) < finalSum:\n",
    "            n -= 1\n",
    "            return list(range(2, 2 * n + 1, 2)) + [finalSum - n * (n + 1)]\n",
    "        else:\n",
    "            n -= 2\n",
    "            return list(range(2, 2 * n + 1, 2)) + [finalSum - n * (n + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        targ = finalSum\n",
    "        n = int(sqrt(targ))\n",
    "\n",
    "        if n*(n+1) == targ:\n",
    "            return list(range(2, 2*n+1, 2))\n",
    "        elif n*(n+1) < targ:\n",
    "            n -= 1\n",
    "            return list(range(2, 2*n+1, 2)) + [targ - n*(n+1)]\n",
    "            \n",
    "        else:\n",
    "            n -= 2\n",
    "            return list(range(2, 2*n+1, 2)) + [targ - n*(n+1)]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2==1:\n",
    "            return []\n",
    "        # print(finalSum//2)\n",
    "        sum_ = 0\n",
    "        for i in range(finalSum//2+1):\n",
    "            print(i)\n",
    "            sum_ = sum_+i*2 \n",
    "            if sum_>finalSum:\n",
    "                print(\"--\")\n",
    "                return [j*2 for j in range(1,i-1)]+[i*2-(sum_-finalSum)+(i-1)*2]\n",
    "            elif sum_==finalSum:\n",
    "                return [j*2 for j in range(1,i+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        n = int(finalSum ** 0.5)\n",
    "        while True:\n",
    "            s = n ** 2 + n\n",
    "            if s > finalSum:\n",
    "                res = list(range(2, 2 * (n + 1), 2))\n",
    "                res.remove(s - finalSum)\n",
    "                return res\n",
    "            elif s == finalSum:\n",
    "                return list(range(2, 2 * (n + 1), 2))\n",
    "            else:\n",
    "                n += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        ans = []\n",
    "        tmp = 2\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        while finalSum:\n",
    "            finalSum -= tmp\n",
    "            if finalSum < 0:\n",
    "                ans.append(finalSum + tmp)\n",
    "                break\n",
    "            ans.append(tmp)\n",
    "            tmp += 2\n",
    "        if ans[-1] in ans[:-1]:\n",
    "            ans = ans[:-2] + [ans[-1] + ans[-2]] \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        ans = []\n",
    "        tmp = 2\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        while finalSum > 0:\n",
    "            finalSum -= tmp\n",
    "            ans.append(tmp)\n",
    "            tmp += 2\n",
    "        return ans if finalSum == 0 else ans[:-2] + [ans[-2] + ans[-1] + finalSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1 or finalSum == 0:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        k = 2\n",
    "        while finalSum > 0 :\n",
    "            res.append(k)\n",
    "            finalSum -= k\n",
    "            k += 2\n",
    "\n",
    "        return res if finalSum == 0 else res[:-2] + [res[-1]+ res[-2] + finalSum]\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maximumEvenSplit(self, a: int) -> List[int]:\n",
    "        if a % 2 == 1:\n",
    "            return []\n",
    "        cnt = 0\n",
    "        path = []\n",
    "        cnt = int((4 * a + 1) ** 0.5)\n",
    "        if cnt % 2 == 1: cnt += 1\n",
    "        # print(cnt)\n",
    "        path  = [ i for i in range(2, cnt+1, 2)]\n",
    "        # print(path)\n",
    "        if cnt * (cnt+2) == 4 * a:\n",
    "            return path\n",
    "        else:\n",
    "            print(path, sum(path), cnt)\n",
    "            idx = path.index(sum(path) - a)\n",
    "            print(path , idx)\n",
    "            path.pop(idx)\n",
    "        return path "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2 == 1:\n",
    "            return []\n",
    "        \n",
    "        maxSplit = []\n",
    "        tempSum = finalSum\n",
    "        for i in range(2,finalSum+1,2):\n",
    "            tempSum = tempSum -i\n",
    "            print(i)\n",
    "            print(tempSum)\n",
    "            if tempSum <= i:\n",
    "                maxSplit.append(i+tempSum)\n",
    "                return maxSplit          \n",
    "                    \n",
    "            else:\n",
    "                maxSplit.append(i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum %2 != 0 :\n",
    "            return [] \n",
    "        finalSum = finalSum//2 \n",
    "        \n",
    "        if finalSum == 1:\n",
    "            ans = [1]\n",
    "        else:\n",
    "            for i in range(1,1000000):\n",
    "                if i*(i+1)//2 >= finalSum :\n",
    "                    ans = [j for j in range(1,i+1)]\n",
    "                    res = finalSum - i*(i+1)//2 \n",
    "                    if res!= 0:\n",
    "                        ans[-1] += res\n",
    "                    break\n",
    "        if len(ans) > 1 and ans[-1] in ans[0:-1]:\n",
    "            ans[-2] = ans[-1]+ans[-2]\n",
    "            ans = ans[0:-1]\n",
    "        ans = [i*2 for i in ans]\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        \n",
    "        finalSum //= 2\n",
    "        res = []\n",
    "        i = 0\n",
    "        while finalSum > 0:\n",
    "            i += 1\n",
    "            if finalSum >= i:\n",
    "                finalSum -= i\n",
    "                res.append(i)\n",
    "            else:\n",
    "                res[-1] = i-1+finalSum\n",
    "                break\n",
    "                \n",
    "        return [x*2 for x in res]\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        #公差为1的等差数列求和：s=n(n+1)//2\n",
    "        if finalSum%2 == 1:\n",
    "            return []\n",
    "        s = finalSum//2\n",
    "\n",
    "        #1、数学解法\n",
    "        # n = math.ceil(sqrt(2*s+0.25)-0.5)\n",
    "        # minus = n*(n+1)//2-s \n",
    "\n",
    "        # return [i*2 for i in range(1,n+1) if i != minus]\n",
    "\n",
    "        #2、贪心解法\n",
    "        i = 1\n",
    "        res = []\n",
    "        while s >= i:\n",
    "            res.append(i)\n",
    "            s -= i\n",
    "            i += 1\n",
    "        if s > 0:\n",
    "            res.append(i)\n",
    "            res.remove(i-s)\n",
    "        return [2*a for a in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        n = finalSum >> 1\n",
    "        all_nums = []\n",
    "        all_sum = 0\n",
    "        for i in range(1, n+1):\n",
    "            if all_sum+i+i+1 < n:\n",
    "                all_sum += i\n",
    "                all_nums.append(i)\n",
    "            elif all_sum+i+i+1 == n:\n",
    "                all_nums.append(i)\n",
    "                all_nums.append(i+1)\n",
    "                return [j*2 for j in all_nums]\n",
    "            elif all_sum+i+i+1 > n:\n",
    "                all_nums.append(n-all_sum)\n",
    "                break\n",
    "        return [j*2 for j in all_nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        finalSum //= 2\n",
    "        res = []\n",
    "        for i in range(1, finalSum + 1):\n",
    "            if finalSum >= i:\n",
    "                res.append(i)\n",
    "                finalSum -= i\n",
    "            else:\n",
    "                res.append(res.pop() + finalSum)\n",
    "                break\n",
    "        return [2*x for x in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2: return []\n",
    "        half = finalSum // 2\n",
    "        res, tot = [], 0\n",
    "        for i in range(1, half + 1):\n",
    "            if tot + i <= half:\n",
    "                res.append(i)\n",
    "                tot += i\n",
    "            else: break\n",
    "        if tot != half:\n",
    "            left = half - tot\n",
    "            need = res[-1] - left + 1\n",
    "            res = res[:need-1] + res[need:] + [left+need]\n",
    "        return [2 * n for n in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        # 最高10**10\n",
    "        if finalSum%2!=0:return []\n",
    "        '''\n",
    "            所有偶数的表达性，肯定是所有都可以表达的\n",
    "            2\n",
    "            4 2+2 --> 4\n",
    "            6 2+2+2 --> 2+4\n",
    "            8 2+2+2+2 --> 2+2+4 --> 2+6 \n",
    "            10 2+2+2+2+2 --> 2+2+2+4 --> 2+2+6 --> 4+6\n",
    "            12 6个2 --> 4个2+4 --> 3个2+6 --> 2+4+6\n",
    "            24 12个2 --> 10个2+4 --> 7个2+4+6 --> 2个2+4+6+8  --> 2+4+6+10\n",
    "            存在2个2时转化为4，\n",
    "            假设某个数=2x， 首先分为 x个2\n",
    "            2(x-2) + 4 \n",
    "            5(x-2) + 4 + 6\n",
    "            销毁2个2、3个2、4个2，不够用了就倒着加\n",
    "        '''\n",
    "        if finalSum==2 or finalSum==4:return [finalSum]\n",
    "        finalSum//=2 # 这么多个2\n",
    "        ans=[]\n",
    "        i=1\n",
    "        '''\n",
    "            target=14\n",
    "            1 2 3 4 不够加了\n",
    "            2 3 4 5 正好\n",
    "            2 3 4 5 --> 4 6 8 12\n",
    "\n",
    "            target =4\n",
    "            1 2 还剩一个\n",
    "            1 3 可以\n",
    "        '''\n",
    "        while i<=finalSum:\n",
    "            finalSum-=i\n",
    "            ans.append(i)\n",
    "            i+=1\n",
    "\n",
    "        # 还剩finalSum个2\n",
    "        n=len(ans)\n",
    "        mod=finalSum%n\n",
    "        count=finalSum//n\n",
    "        for j in range(n-1,-1,-1):\n",
    "            if mod:\n",
    "                ans[j]+=1\n",
    "                mod-=1\n",
    "            ans[j]+=count\n",
    "        return [i*2 for i in ans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum&1:return []\n",
    "        d=finalSum//2\n",
    "        #(1+n)*n//2>=d\n",
    "        #n^2+n-2d>=0\n",
    "        #n=(-1+sqrt(1+8*d))/2\n",
    "        n=ceil((-1+sqrt(1+8*d))/2)\n",
    "        if (1+n)*n//2==d:\n",
    "            return range(2,2*(n+1),2)\n",
    "        r=list(range(1,n))\n",
    "        r[-1]+=d-n*(n-1)//2\n",
    "        return [2*x for x in r]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2:\n",
    "            return []\n",
    "        rst = []\n",
    "        cur = 2\n",
    "        s = 0\n",
    "        while s + cur <= finalSum:\n",
    "            rst.append(cur)\n",
    "            s += cur\n",
    "            cur += 2\n",
    "        if s == finalSum:\n",
    "            return rst\n",
    "        for i, c in enumerate(rst):\n",
    "            if finalSum - s + c > rst[-1]:\n",
    "                return rst[:i] + rst[i+1:] + [finalSum-s+c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int):\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        k = finalSum // 2\n",
    "        largest = int((sqrt(1 + 8 * k) - 1) / 2)\n",
    "        gap = k - largest * (largest + 1) // 2\n",
    "        ans = [2*x for x in list(range(1, largest)) + [largest + gap]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum&1:return []\n",
    "        d=finalSum//2\n",
    "        #(1+n)*n//2>=d\n",
    "        #n^2+n-2d>=0\n",
    "        #n=(-1+sqrt(1+8*d))/2\n",
    "        n=ceil((-1+sqrt(1+8*d))/2)\n",
    "        if (1+n)*n//2==d:\n",
    "            return range(2,2*(n+1),2)\n",
    "        r=list(range(1,n))\n",
    "        r[-1]+=d-n*(n-1)//2\n",
    "        return [2*x for x in r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        finalSum //= 2\n",
    "        n = math.ceil((sqrt(1 + 8 * finalSum) - 1) / 2)\n",
    "        if n * (1 + n) == 2 * finalSum:\n",
    "            return [2 * i for i in range(1, n + 1)]\n",
    "        else:\n",
    "            ret = list(range(1, n))\n",
    "            remain = finalSum - n * (n - 1) // 2\n",
    "            for i in range(1, remain + 1):\n",
    "                ret[-i] += 1\n",
    "            return [2 * v for v in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        finalSum //= 2\n",
    "        n = math.ceil((sqrt(1 + 8 * finalSum) - 1) / 2)\n",
    "        if n * (1 + n) == 2 * finalSum:\n",
    "            return [2 * i for i in range(1, n + 1)]\n",
    "        else:\n",
    "            ret = list(range(1, n))\n",
    "            remain = finalSum - n * (n - 1) // 2\n",
    "            for i in range(1, remain + 1):\n",
    "                ret[-i] += 1\n",
    "            return [2 * v for v in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0: return []\n",
    "        half = finalSum // 2\n",
    "        res = [0]\n",
    "        while half > 0:\n",
    "            if half > res[-1]:\n",
    "                res.append(res[-1]+1)\n",
    "                half -= res[-1]\n",
    "            elif half <= res[-1]:\n",
    "                res[-1]+=half\n",
    "                half = 0\n",
    "        return [2*i for i in res[1:]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#import math\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum%2!=0:\n",
    "            return([])\n",
    "        start=2\n",
    "        ans_all=[start]\n",
    "        times2=[start]\n",
    "        while(times2[-1]<finalSum):\n",
    "            start+=2\n",
    "            ans_all.append(start)\n",
    "            times2.append(start+times2[-1])\n",
    "        #print(ans_all,times2)\n",
    "        if times2[-1]==finalSum:\n",
    "            return(ans_all)\n",
    "        ans_all.pop()\n",
    "        ans_all[-1]+=finalSum-times2[-2]\n",
    "        return(ans_all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 != 0:\n",
    "            return []\n",
    "        finalSum = finalSum / 2\n",
    "        cur_sum = 0\n",
    "        ans = []\n",
    "        cur = 1\n",
    "        while cur_sum < finalSum:\n",
    "            ans.append(cur)\n",
    "            cur_sum += cur\n",
    "            cur += 1\n",
    "        if cur_sum > finalSum:\n",
    "            cur_sum -= cur - 1\n",
    "            ans = ans[:-1]\n",
    "        sub = int(finalSum - cur_sum)\n",
    "        ans[-1] += sub\n",
    "        ans = [2 * i for i in ans]\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 or finalSum < 2:\n",
    "            return []\n",
    "        halfSum = finalSum/2\n",
    "        n = 1\n",
    "        cumSum = 1\n",
    "        while cumSum <= halfSum:\n",
    "            n += 1\n",
    "            cumSum = n * (n+1)/2\n",
    "        out = list(range(1, n))\n",
    "        out.pop()\n",
    "        out.append(int(halfSum-sum(out)))\n",
    "\n",
    "        out = list(map(lambda x: 2*x, out))\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        finalSum //= 2\n",
    "        n = math.ceil((sqrt(1 + 8 * finalSum) - 1) / 2)\n",
    "        if n * (1 + n) == 2 * finalSum:\n",
    "            return [2 * i for i in range(1, n + 1)]\n",
    "        else:\n",
    "            ret = list(range(1, n + 1))\n",
    "            ret.pop(n * (n - 1) // 2 -finalSum - 1)\n",
    "            return [2 * v for v in ret]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2:\n",
    "            return []\n",
    "        \n",
    "        finalSum = finalSum // 2\n",
    "        ansSum = 0\n",
    "        ans = []\n",
    "        for i in range(1, finalSum + 1):\n",
    "            if ansSum + i > finalSum:\n",
    "                break\n",
    "            ans.append(i)\n",
    "            ansSum += i\n",
    "            if ansSum == finalSum:\n",
    "                return [2 * num for num in ans ]\n",
    "        res = finalSum - ansSum\n",
    "        ans[-1] += res\n",
    "        return [2 * num for num in ans ]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        res = []\n",
    "        if finalSum % 2 != 0:\n",
    "            return res\n",
    "        \n",
    "        sumBy2 = finalSum // 2\n",
    "        n = math.floor(math.sqrt(finalSum))\n",
    "        # print(n)\n",
    "        rest = sumBy2 - n * (n + 1) // 2\n",
    "        # print(rest)\n",
    "        res = [i + 1 for i in range(n)]\n",
    "        res[-1] = res[-1] + rest\n",
    "        if n >= 2 and res[-1] <= res[-2]:\n",
    "            tmp = res.pop()\n",
    "            res[-1] += tmp\n",
    "        return [item * 2 for item in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2 == 1:\n",
    "            return []\n",
    "        \n",
    "        twos = finalSum // 2\n",
    "        res = []\n",
    "        cur = 0\n",
    "        num = 1\n",
    "        while cur + num <= twos:\n",
    "            res.append(num)\n",
    "            cur += num\n",
    "            num += 1\n",
    "        \n",
    "        res[-1] += twos - cur\n",
    "        return [num * 2 for num in res]\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumEvenSplit(self, finalSum: int) -> List[int]:\n",
    "        if finalSum % 2:\n",
    "            return []\n",
    "        \n",
    "        finalSum = finalSum // 2\n",
    "        ansSum = 0\n",
    "        ans = []\n",
    "        for i in range(1, finalSum + 1):\n",
    "            if ansSum + i > finalSum:\n",
    "                break\n",
    "            ans.append(i)\n",
    "            ansSum += i\n",
    "            if ansSum == finalSum:\n",
    "                return [2 * num for num in ans ]\n",
    "        res = finalSum - ansSum\n",
    "        ans[-1] += res\n",
    "        return [2 * num for num in ans ]\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
